package com.hzdp.sort;

public class TestSort {

	public static void main(String[] args) {
		int[] array = { 2, 32, 10, 0, 2, 11, 30, 2, 4, 5, 1, 2 };
		mergeSort(array, 0, array.length - 1);
		for (int i : array) {
			System.out.print(i + ",");
		}
	}

	private static void swap(int[] array, int i, int j) {
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}

	private static void mergeSort(int[] array, int s, int e) {
		if (s >= e) {
			return;
		}

		int length = e - s + 1;

		if (length <= 1) {
		} else if (length == 2) {
			if (array[e] < array[s]) {
				swap(array, s, e);
			}
		} else {
			int mid = s + (length >> 1) - 1;
			mergeSort(array, s, mid);
			mergeSort(array, mid + 1, e);
			// merge
			int i = s;
			int j = mid + 1;
			int p = 0;
			int[] tempArray = new int[length];
			while (i <= mid && j <= e) {
				if (array[i] <= array[j]) {
					tempArray[p++] = array[i++];
				} else {
					tempArray[p++] = array[j++];
				}
			}
			if (i > mid) {
				System.arraycopy(array, j, tempArray, p, e - j + 1);
			} else if (j > e) {
				System.arraycopy(array, i, tempArray, p, mid - i + 1);
			}

			System.arraycopy(tempArray, 0, array, s, length);
		}
	}
}
